import java.util.*;

class Solution {
    class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public boolean isSameTree(TreeNode p, TreeNode q) {
         if(p==null&&q==null){
             return true;
         }
         //p、q有一个为空
         if(p==null&&q!=null||p!=null&&q==null){
             return false;
         }
         //两个都不为空，不相等
         if(p.val!=q.val){
             return false;
         }
         //两个都不为空且p=q
         return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //是否为子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        TreeNode cur=root;
        if(root==null||subRoot==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
    //翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root==null||root.left==null&&root.right==null){
            return root;
        }
        TreeNode tmp= root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    //平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
//        int left=MaxLength(root.left);
//        int right=MaxLength(root.right);
//        if (Math.abs(left-right)<=1&&isBalanced(root.right)&&isBalanced(root.left)){
//            return true;
//        }else {
//            return false;
//        }
        return MaxLength(root)>0;
    }
    public int MaxLength(TreeNode root){
        if (root==null){
            return 0;
        }
        int Left=MaxLength(root.left);
        int Right=MaxLength(root.right);
       if(Left>=0&&Right>=0&&Math.abs(Left-Right)<=1){
           return Math.max(Left,Right)+1;
       }else return -1;
    }

    //对称二叉树
    public boolean isSymmetric(TreeNode root){
        if(root==null){
            return true;
        }else {
            return isSymmetric(root.left,root.right);
        }
    }
    public boolean isSymmetric(TreeNode L,TreeNode R){
        if(L==null&&R==null){
            return true;
        }
        if(L==null&&R!=null||L!=null&&R==null){
                return false;
        }
        if(L.val!= R.val){
            return false;
        }
        //错误写法，引用不能直接比较，要通过val比较
//        if(L.left==R.right&&L.right==R.left){
//            return isSymmetric(L.left,R.right)&&isSymmetric(L.right,R.left);
//        }else {
//            return false;
//        }
        return isSymmetric(L.left,R.right)&&isSymmetric(L.right,R.left);
    }




    //层序遍历
    public void order(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){
            return;
        }
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.println(cur.val+" ");
            if(cur.left!=null){
                queue.add(cur.left);
            }
            if (cur.right!=null){
                queue.add(cur.right);
            }
        }

    }
    //非递归
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            List<Integer> l=new ArrayList<>();
            while (size!=0){
                TreeNode cur=queue.poll();
                size--;
                l.add(cur.val);
                if(cur.left!=null){
                    queue.add(cur.left);
                }
                if (cur.right!=null){
                    queue.add(cur.right);
                }
            }
            list.add(l);
        }
        return list;
    }
    //最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode Left=lowestCommonAncestor(root.left,p,q);
        TreeNode Right=lowestCommonAncestor(root.right,p,q);
        if(Left!=null&&Right!=null){
            return root;
        }
        if(Left!=null){
            return Left;
        }else {
            return Right;
        }
    }
    //栈实现公共祖先
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
    Stack<TreeNode> stackp=new Stack<>();
    Stack<TreeNode> stackq=new Stack<>();
    getpath(root,p,stackp);
    getpath(root,q,stackq);
    int sizep= stackp.size();
    int sizeq=stackq.size();
    int size=sizep-sizeq;
    if (size>0){
        while (size!=0){
            stackp.pop();
            size--;
        }
    }else {
        while (size!=0){
            stackq.pop();
            size--;
        }
    }
    while (!stackp.isEmpty()&&!stackq.isEmpty()){
        TreeNode curp=stackp.pop();
        TreeNode curq=stackq.pop();
        if(curp.equals(curq)){
            return curp;
        }
    }

    return null;
    }
    public  Boolean getpath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root==null||node==null){
            return false;
        }
        stack.push(root);
        if (root==node){
            return true;
        }
        boolean Left=getpath(root.left,node,stack);
        if (Left==true){
            return true;
        }
        boolean Right=getpath(root.right,node,stack);
        if (Right==true){
            return true;
        }
        stack.pop();
        return false;
    }

    //根据前序遍历，中序遍历创建二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {

    return buildTreeChild(preorder,inorder,0,inorder.length-1);

    }
    public int i=0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int ib,int ie){
        if(ib>ie){
            return null;
        }
        TreeNode root=new TreeNode(preorder[i]);
        int index=Find(preorder[i],inorder,ib,ie);
        if (index==-1){
            return null;
        }
        i++;
        root.right=buildTreeChild(preorder, inorder, index+1, ie);
        root.left=buildTreeChild(preorder, inorder, ib, index-1);

        return root;
    }
    public int Find(int a,int[] arr,int ib,int ie){
        for (int j=ib;j<=ie;j++){
            if(arr[j]==a){
                return j;
            }
        }
       return -1;
    }

    //根据后续和中序创建二叉树
    int post;
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        post=postorder.length-1;
        return buildTreeChild2(inorder,postorder,0,inorder.length-1);
    }
    public TreeNode buildTreeChild2(int[] inorder, int[] postorder,int ib,int ie) {

        if(ib>ie){
            return null;
        }
        TreeNode root=new TreeNode(postorder[post]);
        int index=Find(postorder[post],inorder,ib,ie);
        if (index==-1){
            return null;
        }
        post--;
        root.right=buildTreeChild2(inorder,postorder,index+1,ie);
        root.left=buildTreeChild2(inorder,postorder,ib,index-1);

        return root;
    }
    //前序遍历创建字符串
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder =new StringBuilder();
        tree2str(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void tree2str(TreeNode root,StringBuilder stringBuilder) {
        if(root==null){
            return ;
        }
        stringBuilder.append(root.val);
        if(root.left!=null){
            stringBuilder.append("(");
            tree2str(root.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            //root.left==null
            if(root.right!=null){
                stringBuilder.append("( )");
            }else {
               //root.left==null &&root.left==null
                return ;
            }
        }

        if(root.right!=null){
            stringBuilder.append("(");
            tree2str(root.right,stringBuilder);
            stringBuilder.append(")");
        }else {
            //root.right==null
            return;
        }
    }
    //前序遍历非递归
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        res.add(root.val);
        List<Integer> Left=preorderTraversal(root.left);
        res.addAll(Left);
        List<Integer> Right=preorderTraversal(root.right);
        res.addAll(Right);
        return res;

    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if (root==null){
            return res;
        }
        List<Integer> Left=inorderTraversal(root.left);
        res.addAll(Left);
        res.add(root.val);
        List<Integer> Right=inorderTraversal(root.right);
        res.addAll(Right);
        return res;
    }
    void preorder(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return;
        }
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                System.out.println(cur.val+" ");
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }

    }
    void inorder(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return;
        }
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.println(top.val+" ");
            cur=top.right;
        }

    }
    void postorder(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return;
        }
        TreeNode cur=root;
        TreeNode prev=null;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();{
                if (top.right==null||top.right==prev){
                    stack.pop();
                    System.out.println(top.val+" ");
                    prev=top;
                }else {
                    cur=top.right;
                }
            }

        }

    }







}



